package com.cjm.algorithm.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/minimum-falling-path-sum/description/">url</a>
 * <p>
 * 这个题目，我先想到是什么呢？
 * 1、第一排， 选择一个数
 * 2、第二排，再选择一个数
 * 3、第n排， 再接着选择一个数
 * ....
 * <p>
 * 这样， 我们就会选择了n个数， 那么这n个数， 是不是最小的呢？不一定， 不到最后一个， 我觉得都是不知道的， 万一最后一个数很小呢，是吧
 * 那么再想一个， 那就是得比较一下， 如果， 当前的前n个数的和， 已经大于前面某些数的和了， 那么它就不会是最小了， 这算是一个短路点
 * <p>
 * 1、将大问题分解成一个一个的小问题；[一个一个的小问题]
 * 2、动态规划有【选或不选】和【枚举选】两种基本方式；
 * <p>
 * 打算我们从dfs(r, c)出发 -> dfs(r-1, c-1_, dfs(r-1, c), dfs(r-1, c+1)
 * <p>
 * 那么公式为：dfs(r, c) = min(dfs(r-1, c-1), dfs(r-1, c), dfs(r-1, c+1)) + 矩阵[r][c];
 * <p>
 * 1, 2, 3
 * 4, 5, 6
 * 7, 8, 9
 * <p>
 * mtrix[0, 0] = 1;
 * mtrix[0, 1] = 2;
 * mtrix[0, 2] = 3;
 * mtrix[1, 0] = 4;
 * mtrix[1, 1] = 5;
 * mtrix[1, 2] = 6;
 * mtrix[2, 0] = 7;
 * mtrix[2, 1] = 8;
 * mtrix[2, 2] = 9;
 */
public class Ti931 {
    Map<String, Integer> meme;

    // 2024-09-21 22:46:49
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        // 这里相当于剪枝
        meme = new HashMap<>(n);
        // 最小值
        int res = Integer.MAX_VALUE;

        // 遍历第一行的每一列
        for (int col = 0; col < n; col++) {
            res = Math.min(res, dp(matrix, n - 1, col));
        }

        return res;
    }

    int dp(int[][] matrix, int row, int col) {
        // 剪枝
        String key = row + "," + col;
        if (meme.containsKey(key)) {
            return meme.get(key);
        }
        // 边界值
        if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length) {
            return Integer.MAX_VALUE;
        }
        // 其实这里就是最后一行了
        if (row == 0) {
            return matrix[row][col];
        }
        int i = matrix[row][col] +
                Math.min(
                        Math.min(dp(matrix, row - 1, col),
                                dp(matrix, row - 1, col - 1)
                        ), dp(matrix, row - 1, col + 1));
        meme.put(key, i);
        return i;
    }
}
